#include <common.h>

class Solution {
public:
    int jump(vector<int>& nums) {
        int r_range=0;
        int cnt=0;
        int n=nums.size();
        while(r_range<n-1) {
            //取出当前最远距离
            int range=nums[r_range];
            //若发现当前已经可以抵达终点
            if(r_range+range>=n-1)return cnt+1;
            int max_t=-1;
            int max_potential=-1;
            for(int i=r_range+1;i<=r_range+range;i++) {
                int potential=nums[i]+i;
                if(potential>=max_potential) {
                    max_potential=potential;
                    max_t=i;
                }
            }
            r_range=max_t;
            cnt++;
        }
        return cnt;
    }
};

int main() {
    const auto sp=new Solution();
    vector<int> nums{2,3,1,2,4,2,3};
    const int jump = sp->jump(nums);
    cout<<jump<<endl;
    return 0;
}